package cn.qyd.kaoshi;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

/**
 * @author 邱运铎
 * 窗口滑动 求解 LCR 017. 最小覆盖子串
 * @date 2024-03-24 16:26
 */
public class MinSonStrUpgrade {
    private static HashMap<Character,Integer> tMap = new HashMap<>();
    private static HashMap<Character,Integer> strMap = new HashMap<>();
    public static void main(String[] args) {
//        String s = "ADOBECODEBANC";
//        String t = "ABC";
//        String s = "abc";
//        String t = "ac";
        String s = "a";
        String t = "a";
        int sLen = s.length();
        int tLen = t.length();

        for (int i = 0; i < tLen; i++) {
            char tChar = t.charAt(i);
            tMap.put(tChar,tMap.getOrDefault(tChar,0) + 1);
        }

        int left = 0, right = 0, minLen = Integer.MAX_VALUE, minLeft = -1, minRight = -1;

        while (right < sLen) {
            char rightChar = s.charAt(right);
            if (tMap.containsKey(rightChar)) {
                strMap.put(rightChar,strMap.getOrDefault(rightChar,0) + 1);
            }

            while (check() && left <= right) {
                if (minLen > right - left +1) {
                    System.out.println(right);
                    minLen = right - left +1;
                    minLeft = left;
                    minRight = right;
                }

                char leftChar = s.charAt(left);
                if (tMap.containsKey(leftChar)) {
                    strMap.put(leftChar,strMap.getOrDefault(leftChar,0) - 1);
                }

                left++;
            }
            right++;
        }

        System.out.println(minLen);
        System.out.println(minLeft < 0 ? "" : s.substring(minLeft,minRight + 1));

    }

    public static boolean check() {
        Iterator<Map.Entry<Character, Integer>> it = tMap.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<Character, Integer> entry = it.next();
            if (strMap.containsKey(entry.getKey())) {
                if (strMap.get(entry.getKey()) < entry.getValue()) {
                    return false;
                }
            } else {
                return false;
            }
        }
        return true;
    }
}
